package com.tgy.algorithm.base._二叉树;

import java.util.LinkedList;

public class _二叉树获取最大一层的数量 {

    public static BiTreeNode generalBiTreeNode() {
        /**
         *              1
         *         2           3
         *            4     5
         *
         */
        BiTreeNode root = new BiTreeNode(1);
        root.left = new BiTreeNode(2);
        root.right = new BiTreeNode(3);
        root.left.left = new BiTreeNode(4);
        root.left.right = new BiTreeNode(4);
        root.right.left = new BiTreeNode(5);

        return root;
    }

    public static int getMaxLevelNum(BiTreeNode root) {

        if (root == null) {
            return 0;
        }

        int maxLevel = 0;
        int levelCount = 1;
        BiTreeNode curentEndNode = root;
        BiTreeNode nextEndNode = root;
        LinkedList<BiTreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            BiTreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
                nextEndNode = node.left;
            }

            if (node.right != null) {
                queue.offer(node.right);
                nextEndNode = node.right;
            }

            if (node == curentEndNode) {
                maxLevel  = Math.max(levelCount, maxLevel);
                levelCount = 1;
                curentEndNode = nextEndNode;
            }else {
                levelCount++;
            }
        }

        return maxLevel;
    }

    public static void main(String[] args) {
        BiTreeNode root = generalBiTreeNode();
        int maxLevelNum = getMaxLevelNum(root);
        System.out.println(maxLevelNum);
    }
}
